The present invention relates generally to automatic sorting, and specifically to automatic location of text or other well-defined features on material being sorted.
A crucial problem in automatic sorting systems, well known in the art, is the location of desired fields on the surface of an object whose image is captured and analyzed. Typically the fields have some predefined visual structure having a geometric component, for example, a text field comprising sets of alphanumeric characters in a substantially linear layout. In the context of the present patent application and in the claims, such a field is referred to as a structured field. Existing approaches to this problem comprise binarization of an image as a first step, wherein a gray-scale image is first converted to binary form, and wherein, for the case of text location, domain-oriented heuristics are used as a second step. An example of this approach is described in an article titled xe2x80x9cPostal Address Block Location in Real Time,xe2x80x9d by Palumbo et al., in the July, 1992, issue of Computer, which is incorporated herein by reference.
Although binarization of images allows large volumes of image data to be processed quickly, methods involving binarization have several drawbacks, since no perfect binarization is known. As a result some image fields that are being searched for will be consistently discarded, since binarization reduces the available information about the image. Furthermore, for large images, such as images of postal packets, the time required for binarization is substantial.
In searching for a text field such as an address block in an automatic parcel sorting system, the text field must always be found, or else the entire sorting process fails. Also, the number of falsely identified blocks must be minimal, in order not to generate too much work for the rest of the modules of the sorting system.
It is an object of some aspects of the present invention to provide an improved method and apparatus for location of structured fields in an image.
It is a further object of some aspects of the present invention to provide an improved method and apparatus for location of text fields in an image.
It is an object of some aspects of the present invention to provide an improved method and apparatus for automatic sorting of mail.
In preferred embodiments of the present invention, a gray-scale image of an object having one or more structured fields, most preferably text fields, is generated. Preferably, the image is generated by a line imaging system, and the generated image is digitized and transferred in digital form to a central processing unit. Most preferably, the processing unit comprises dedicated hardware including a first and a second processing stage, described in more detail below, which operate on the digitized image sequentially in real time. Alternatively, the processing unit comprises a mixture of dedicated hardware and general-purpose, software-driven computing elements. After the stages have operated on the digitized image, the processing unit determines areas in the image where the results indicate there are text fields, according to predetermined conditions incorporated into the processing stages.
In some preferred embodiments of the present invention, the digitized image data of the object is processed by the first processing stage, which detects areas of the image having a high probability of containing text, herein termed xe2x80x9ctext kernels.xe2x80x9d Most preferably, the algorithm operates on an array of image pixels, herein termed xe2x80x9canchor points,xe2x80x9d which are separated by predetermined distances. Positions of text kernels are determined by locating points, herein termed xe2x80x9cdominant points,xe2x80x9d around the anchor points which have substantial gray-scale differences compared to horizontally or vertically adjacent points. Areas around the text kernels are analyzed, and those considered by the processing stage to have a high probability of containing text are grouped together. The first stage concludes by building a first map of text regions based around the text kernels.
The output of the first processing stage is processed by the second processing stage, wherein the text regions found in the first stage are analyzed and refined further. Preferably, each of the text regions has its anchor points reallocated, so that the anchor points are separated by distances substantially smaller than in the first stage. Preferably the anchor points separation for the second stage is half the separation of the first stage. As described for the first stage, regions having a high probability of containing text are identified. The second stage concludes by outputting positions of regions of interest (ROIs) likely to contain text, together with an associated ranking for each ROI, made in accordance with geometrical characteristics of the ROI.
In some preferred embodiments of the present invention, the gray-scale image comprises an image of an object, such as a parcel, to be sorted for mail delivery. Preferably, the parcel travels on a conveyor belt system comprising means for sorting parcels into appropriate groups. For example, the conveyer belt system is able to sort parcels into those with no identified text fields, those with one text field, and those with a plurality of possible text fields. Alternatively, other methods of sorting, as are known in the art, are used. After determination of regions on the parcel which include text fields, as described above, the parcel is sorted into the appropriate group by the processing unit operating on the sorting system. The text field is then read and interpreted, preferably using an optical character recognition algorithm, as is known in the art, and the parcel is routed for delivery accordingly.
The present invention enables very fast detection of fields within an image which have well-defined directional properties, with substantially greater accuracy, and with substantially fewer falsely identified blocks, compared to methods at present known in the art.
There is therefore provided, in accordance with a preferred embodiment of the present invention, a method for locating a structured field in a gray-scale image of an object, including:
choosing a plurality of anchor points in the image, each anchor point having a gray-scale value associated therewith;
determining for each anchor point a horizontal variation dependent on a difference between the gray-scale value of the anchor point and the gray-scale value of a horizontally neighboring anchor point and a vertical variation dependent on a difference between the gray-scale value of the anchor point and the gray-scale value of a vertically neighboring anchor point;
defining as vertically or horizontally dominant respectively those anchor points whose vertical and horizontal variations obey a first or a second predefined condition;
identifying one or more kernels in the image, each such kernel comprising a group of anchor points in predetermined mutual proximity and satisfying a third predefined condition relating the number of vertically-dominant and horizontally-dominant anchor points in the group; and
locating the structured field in the image using the one or more kernels.
Preferably, the structured field includes an alphanumeric text field.
Alternatively, the text field includes an address field in a mailed object.
Preferably, the method includes sorting the object responsive to the structured field that is located.
Preferably, choosing the plurality of anchor points includes choosing the anchor points to be at the vertices of congruent contiguous rectangles.
Preferably, locating the structured field includes dividing the image into a plurality of regions and finding one or more of the regions which have large numbers of kernels therein relative to others of the regions.
Alternatively, finding the one or more of the regions includes assigning a ranking level to each of the regions indicative of a likelihood that the region has a desired characteristic.
Further alternatively, assigning the ranking level includes evaluating kernels in peripheral regions adjacent to the one or more regions.
Alternatively, assigning the ranking level includes assigning a ranking responsive to respective numbers of vertically dominant points and horizontally dominant points in the one or more regions.
Further alternatively, locating the structured field includes using an iterative location method, including choosing additional anchor points in the one or more regions and repeating with respect to the additional anchor points the steps of determining the horizontal and vertical variations, defining the vertically- and horizontally-dominant points and identifying the one or more kernels.
Alternatively, choosing the additional anchor points includes choosing anchor points mutually more closely spaced than the anchor points outside the one or more regions.
Preferably, the first predefined condition includes that the vertical variation be above a predetermined threshold and exceed the horizontal variation by a predetermined factor.
Preferably, the second predefined condition includes that the horizontal variation be above a predetermined threshold and exceed the vertical variation by a predetermined factor.
Preferably, the third predefined condition includes that there be at least one vertically dominant point and at least one horizontally dominant point within the group.
There is further provided, in accordance with a preferred embodiment of the present invention, a method for locating a structured field in a gray-scale image of an object, including:
choosing a plurality of anchor points in the image, each anchor point having a gray-scale value associated therewith;
determining for each anchor point, a horizontal variation dependent on a difference between the gray-scale value of the anchor point and the gray-scale value of a horizontally neighboring anchor point and a vertical variation dependent on a difference between the gray-scale value of the anchor point and the gray-scale value of a vertically neighboring anchor point;
defining as vertically-dominant those anchor points whose vertical variations exceed their horizontal variations by a predefined factor, and as horizontally-dominant those anchor points whose horizontal variations exceed their vertical variations by a predefined factor; and
locating the structured field in the image responsive to the locations of at least some of the vertically-dominant and horizontally-dominant anchor points.
Preferably, locating the structured field includes locating a text field.
Alternatively, locating the structured field includes finding a region of the image including a mixture of horizontally- and vertically-dominant anchor points.
There is further provided, in accordance with a preferred embodiment of the present invention, a method for sorting an object marked with information in a structured field thereon, including:
capturing a gray-scale image of the object;
choosing a plurality of anchor points in the image, each anchor point having a gray-scale value associated therewith;
determining for each anchor point, a horizontal variation dependent on a difference between the gray-scale value of the anchor point and the gray-scale value of a horizontally neighboring anchor point and a vertical variation dependent on a difference between the gray-scale value of the anchor point and the gray-scale value of a vertically neighboring anchor point;
defining as vertically or horizontally dominant those anchor points whose vertical and horizontal variations respectively obey a first or a second predefined condition;
identifying one or more kernels in the image, each such kernel comprising a group of anchor points in predetermined mutual proximity and satisfying a third predefined condition relating the number of vertically-dominant and horizontally-dominant anchor points in the group;
locating the structured field using the one or more kernels;
deciphering information contained in the structured field; and
routing the object responsive to the deciphered information.
There is further provided, in accordance with a preferred embodiment of the present invention, apparatus for locating a structured field in a gray-scale image of an object, including:
an image capture device which forms the gray-scale image of the object; and
an image processing unit which:
chooses a plurality of anchor points in the image;
associates with each anchor point a gray-scale value;
determines for each anchor point a horizontal variation dependent on a difference between the gray-scale value of the anchor point and the gray-scale value of a horizontally neighboring anchor point and a vertical variation dependent on a difference between the gray-scale value of the anchor point and the gray-scale value of a vertically neighboring anchor point;
defines as vertically or horizontally dominant respectively those anchor points whose vertical and horizontal variations obey a first or a second predefined condition;
identifies one or more kernels in the image, each such kernel including a group of anchor points in predetermined mutual proximity and satisfying a third predefined condition relating the number of vertically-dominant and horizontally-dominant anchor points in the group; and
locates the structured field in the image using the one or more kernels.
Preferably, the structured field includes an alphanumeric text field.
Alternatively, the text field includes an address field in a mailed object.
Further alternatively, the apparatus includes an object sorter which sorts the object responsive to the structured field that is located.
There is further provided, in accordance with a preferred embodiment of the present invention, apparatus for locating a structured field in a gray-scale image of an object, including:
an image capture device which forms the gray-scale image of the object; and
an image processing unit which:
chooses a plurality of anchor points in the image;
associates with each anchor point a gray-scale value;
determines for each anchor point, a horizontal variation dependent on a difference between the gray-scale value of the anchor point and the gray-scale value of a horizontally neighboring anchor point and a vertical variation dependent on a difference between the gray-scale value of the anchor point and the gray-scale value of a vertically neighboring anchor point;
defines as vertically-dominant those anchor points whose vertical variations exceed their horizontal variations by a predefined factor, and as horizontally-dominant those anchor points whose horizontal variations exceed their vertical variations by a predefined factor; and
locates the structured field in the image responsive to the locations of at least some of the vertically-dominant and horizontally-dominant anchor points.
There is further provided, in accordance with a preferred embodiment of the present invention, apparatus for sorting an object marked with information in a structured field thereon, including:
an image capture device which forms the gray-scale image of the object;
an image processing unit which:
chooses a plurality of anchor points in the image;
associates with each anchor point a gray-scale value;
determines for each anchor point, a horizontal variation dependent on a difference between the gray-scale value of the anchor point and the gray-scale value of a horizontally neighboring anchor point and a vertical variation dependent on a difference between the gray-scale value of the anchor point and the gray-scale value of a vertically neighboring anchor point;
defines as vertically or horizontally dominant those anchor points whose vertical and horizontal variations respectively obey a first or a second predefined condition;
identifies one or more kernels in the image, each such kernel including a group of anchor points in predetermined mutual proximity and satisfying a third predefined condition relating the number of vertically-dominant and horizontally-dominant anchor points in the group;
locates the structured field using the one or more kernels;
deciphers information contained in the structured field; and
an object router which routs the object responsive to the deciphered information.
The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the drawings in which: